package javase.base;

/**
 * GCD：最大公约数
 * User: Realfighter
 * Date: 2015/1/21
 * Time: 9:09
 */
public class TestGCD {

    public static void main(String[] args) {
        int num1 = 22;
        int num2 = 4;
        System.out.println("[" + num1 + "," + num2 + "]的最大公约数为：" + getGCD(num1, num2));
    }

    /**
     * 辗转相除法求两个数的最大公约数
     *
     * @param num1
     * @param num2
     * @return
     */
    private static int getGCD(int num1, int num2) {
        int _num2 = Math.max(num2, num1);
        int _num1 = Math.min(num2, num1);
        int temp;
        while (true) {
            if (_num1 == 0) {
                throw new RuntimeException("除数不可为0！");
            }
            if (_num2 % _num1 == 0) {
                return _num1;
            } else {
                temp = _num1;
                _num1 = _num2 % _num1;
                _num2 = temp;
            }
        }
    }


}
